package 数组算法;

import java.util.Arrays;

public class sortColors75 {

    public void sortColors(int[] nums) {
        Arrays.sort(nums);
    }

    /**
     * 采用的额双指针的方式的来构建
     * 我们可以考虑对数组进行两次遍历。在第一次遍历中，我们将数组中所有的 0交换到数组的头部。在第二次遍历中，
     * 我们将数组中所有的 1交换到头部的 0 之后。此时，所有的 22 都出现在数组的尾部，这样我们就完成了排序。
     *
     * @param nums
     */
    public void sortColorsV2(int[] nums) {
        int n = nums.length;
        int ptr = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[ptr];
                nums[ptr] = temp;
                ++ptr;
            }
        }
        for (int i = ptr; i < n; ++i) {
            if (nums[i] == 1) {
                int temp = nums[i];
                nums[i] = nums[ptr];
                nums[ptr] = temp;
                ++ptr;
            }
        }
    }

    /**
     * 方法一需要进行两次遍历,我们可以额外使用一个指针，即使用两个指针分别用来交换 00 和 11。
     *
     * @param nums
     */
    public void sortColorsV3(int[] nums) {
        int n = nums.length;
        int p0 = 0, p1 = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 1) {
                int temp = nums[i];
                nums[i] = nums[p1];
                nums[p1] = temp;
                ++p1;
            } else if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[p0];
                nums[p0] = temp;
                if (p0 < p1) {
                    temp = nums[i];
                    nums[i] = nums[p1];
                    nums[p1] = temp;
                }
                ++p0;
                ++p1;
            }
        }
    }
}
